import { CheckAns } from "./CheckAns";

namespace LeetCode0424CharacterReplacement {

    /**
     * 解题思路: 一个个试下去...(暂时没想到别的)
     * @param s 一个仅由大写英文字母组成的字符串
     * @param k 总共可最多替换 k 次
     */
    function characterReplacement(s: string, k: number): number {
        // 移除非法情况
        if (!s || s.length == 0 || k < 0) return 0;
        // 特例处理
        if (s.length <= k + 1) return s.length;

        let ans: number = 0;    // 最终想要的结果
        for (let pos = 0; pos < s.length; pos++) {
            const char1: string = s.charAt(pos);
            let cnt: number = 1;
            let fixed: number = 0;  // 修改字符串次数
            for (let pj = pos + 1; pj < s.length; pj++) {
                const char2 = s.charAt(pj);
                if (char2 == char1) {
                    cnt++;
                }
                else if (char2 != char1 && fixed < k) {
                    cnt++;
                    fixed++;
                }
                else
                    break;
            }
            if (ans < cnt)
                ans = cnt;
        }
        // 错误修正：第一个字符串漏处理
        if (s.length >= 2 && k >= 1 && s[0] != s[1]) {
            const char1: string = s[1];
            let cnt: number = 1;
            let fixed: number = 1;  // 修改字符串次数
            for (let pj = 1; pj < s.length; pj++) {
                const char2 = s.charAt(pj);
                if (char2 == char1) {
                    cnt++;
                }
                else if (char2 != char1 && fixed < k) {
                    cnt++;
                    fixed++;
                }
                else
                    break;
            }
            if (ans < cnt)
                ans = cnt;
        }

        return ans;
    };

    // 改版，性能优化
    function characterReplacement1(s: string, k: number): number {
        // 移除非法情况
        if (!s || s.length == 0 || k < 0) return 0;
        // 特例处理
        if (s.length <= k + 1) return s.length;

        let ans: number = 0;    // 最终想要的结果
        let pos: number = 0;
        let npos: number = 0;   // 下次检测的位置
        while (pos < s.length) {
            const char1: string = s.charAt(pos);
            let cnt: number = 1;
            npos = 0;
            let fixed: number = 0;  // 修改字符串次数
            for (let pj = pos + 1; pj < s.length; pj++) {
                const char2 = s.charAt(pj);
                if (char2 == char1) {
                    cnt++;
                }
                else if (char2 != char1 && fixed < k) {
                    cnt++;
                    fixed++;
                    if (npos == 0)
                        npos = pj;
                }
                else
                    break;
            }
            if (ans < cnt)
                ans = cnt;
            pos = npos > 0 ? npos : (pos + 1);
        }
        // 特殊处理第一个字符串
        if (s.length >= 2 && k >= 1 && s[0] != s[1]) {
            const char1: string = s[1];
            let cnt: number = 1;
            let fixed: number = 1;  // 修改字符串次数
            for (let pj = 1; pj < s.length; pj++) {
                const char2 = s.charAt(pj);
                if (char2 == char1) {
                    cnt++;
                }
                else if (char2 != char1 && fixed < k) {
                    cnt++;
                    fixed++;
                }
                else
                    break;
            }
            if (ans < cnt)
                ans = cnt;
        }

        return ans;
    }

    // 双指针
    function characterReplacement2(s: string, k: number): number {
        // 移除非法情况
        if (!s || s.length == 0 || k < 0) return 0;
        // 特例处理
        if (s.length <= k + 1) return s.length;

        let charCnt: number[] = new Array(26).fill(0);
        let left = 0;
        let right = 0;
        let maxLen = 0;
        while (right < s.length) {
            const charIdx: number = s.charCodeAt(right) - 'A'.charCodeAt(0);
            charCnt[charIdx]++;
            maxLen = Math.max(maxLen, charCnt[charIdx]);
            if (right - left + 1 - maxLen > k) {
                charCnt[s.charCodeAt(left) - 'A'.charCodeAt(0)]--;
                left++;
            }
            right++;
        }
        return right - left;
    }

    // test
    const testData: { s: string, k: number, ans: number }[] = [
        { s: "ABBB", k: 2, ans: 4 },
        { s: "ABAB", k: 2, ans: 4 },
        { s: "AABABBA", k: 1, ans: 4 }
    ];
    for (const data of testData) {
        const ans = characterReplacement2(data.s, data.k);
        CheckAns(data, ans);
    }
}